package longest_palindrome;

import java.util.HashSet;
import java.util.Set;

/**
 * 输入:
 * "abccccdd"
 * <p>
 * 输出:
 * 7
 * <p>
 * 解释:
 * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 * <p>
 * 我们上面已经知道了什么是回文串？现在我们考虑一下可以构成回文串的两种情况：
 * <p>
 * 字符出现次数为双数的组合
 * 字符出现次数为偶数的组合+单个字符中出现次数最多且为奇数次的字符
 */
public class Solution {

    public static int longestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        Set<Character> set = new HashSet<>();
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!set.contains(c)) {
                set.add(c);
            } else {
                set.remove(c);
                cnt++;
            }
        }
        return set.isEmpty()? cnt * 2: cnt * 2 + 1;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("abccccdd"));
    }
}
